class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int left, int right){
        if( left>=right )
            return;
        int mid = (left+right) >> 1;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        int l = left, r = mid+1;
        int[] tmp = new int[right-left+1];
        int index = 0;
        while (l<=mid && r<=right){
            if( nums[l]<=nums[r] ){
                tmp[index++] = nums[l++];
            }else{
                tmp[index++] = nums[r++];
            }
        }
        while (l<=mid){
            tmp[index++] = nums[l++];
        }
        while (r<=right){
            tmp[index++] = nums[r++];
        }
        for(int i=0; i<index; i++){
            nums[left+i] = tmp[i];
        }
    }
}